/*
 * @lc app=leetcode.cn id=338 lang=java
 *
 * [338] 比特位计数
 */

// @lc code=start
class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for(int i = 0; i<= num ;i++){
            res[i] = res[i>>1] + (i & 1);
            // i>>1会把最低位去掉，因此i>>1也是比i小的，同样也是在前面的数组里算过。
            // 最低位是0，则之前算过，最低位是1，则+1即可
        }
        return res;
    }
}
// @lc code=end

